#pragma once

template <typename T>
class WList
{
private:
    struct Node
    {
        T value;
        Node *next = nullptr;
        Node *pre = nullptr;
    };

    Node *_head = nullptr;
    long long int _size = 0;

public:
 ////////////////////////////////////////////////////////////////////////////////
    class iterator
    {
    public:
        typedef T valueType;
        typedef T* pointer;
        typedef T& reference;

        iterator(Node *node = nullptr)
        {
            _node = node;
        }

        virtual ~iterator() {}

        // 从这里也能看出来，++i的性能要高些
        iterator& operator ++() // ++i重载
        {
            _node = _node->next;
            return *this;
        }

        iterator operator ++(int) // i++重载
        {
            iterator temp = *this;
            _node = _node->next;
            return temp;
        }

         // 从这里也能看出来，--i的性能要高些
        iterator& operator --() // --i重载
        {
            _node = _node->pre;
            return *this;
        }

        iterator operator --(int) // i--重载
        {
            iterator temp = *this;
            _node = _node->pre;
            return temp;
        }

        bool operator == (const iterator &other)
        {
            return (this->_node == other._node);
        }

        bool operator != (const iterator &other)
        {
            return (this->_node != other._node);
        }

        T* operator -> ()
        {
            return &(_node->value);
        }

        T& operator * ()
        {
            return _node->value;
        }

        iterator& operator + (int num) // i + 5的重载
        {
            for (int i = 0; i < num; ++i)
            {
                _node = _node->next;
            }
            return *this;
        }

        iterator& operator - (int num) // i - 5的重载
        {
            for (int i = 0; i < num; ++i)
            {
                _node = _node->pre;
            }
            return *this;
        }

    public:
        Node *_node = nullptr;
    };
////////////////////////////////////////////////////////////////////////////////

    WList()
    {
        _head= new Node();
        _head->next = _head; // next指向链表头部
        _head->pre = _head; // pre指向链表尾部
    }

    virtual ~WList()
    {
        delete _head;
        _head =  nullptr;
    }

    iterator begin()
    {
        return iterator(_head->next);
    }

    iterator end()
    {
        return iterator(_head);
    }

    iterator insert(iterator pos, const T &value)
    {
        Node *insertNode = new Node();
        insertNode->value = value;
        Node *currentNode = pos._node;
        Node *nextNode = currentNode->next;
        currentNode->next = insertNode;
        insertNode->pre = currentNode;
        nextNode->pre = insertNode;
        insertNode->next = nextNode;
        _size++;
        return ++pos;
    }

    iterator erase(iterator pos)
    {
        if (_size <= 0)
        {
            return end();
        }

        Node *preNode = pos._node->pre;
        Node *nextNode = pos._node->next;
        preNode->next = nextNode;
        nextNode->pre = preNode;
        delete pos._node;
        _size--;
        return iterator(nextNode);
    }

    void push_back(const T &value)
    {
        insert(--end(), value);
    }

    bool pop_back(T &value)
    {
        if (_size <= 0)
        {
            return false;
        }

        Node *lastNode = _head->pre;
        value = lastNode->value;
        erase(--end());

        return true;
    }

    void push_front(const T &value)
    {
        insert(begin(), value);
    }

    bool pop_front(T &value)
    {
        if (_size <= 0)
        {
            return false;
        }

        Node *firstNode = _head->next;
        value = firstNode->value;
        erase(begin());

        return true;
    }

    long long int size()
    {
        return _size;
    }

    bool empty()
    {
        return (_size == 0);
    }
};
